package com.michael.tree.btree.demo;

public class BTree {
    BTreeNode root; // Pointer to root node
    int t;  // Minimum degree

    public BTree(int t) {
        this.t = t;
    }
    void traverse()
    {
        if (root != null) root.traverse();
    }
    BTreeNode search(int k)
    {
        return (root == null)? null : root.search(k);
    }
    void insert(int k){
        // If tree is empty
        if (root == null)
        {
            // Allocate memory for root
            root = new BTreeNode(t, true);
            root.keys[0] = k;  // Insert key
            root.n = 1;  // Update number of keys in root
        }
        else // If tree is not empty
        {
            // If root is full, then tree grows in height
            if (root.n == 2*t-1)
            {
                // Allocate memory for new root
                BTreeNode s = new BTreeNode(t, false);

                // Make old root as child of new root
                s.c[0] = root;

                // Split the old root and move 1 key to the new root
                s.splitchild(0, root);

                // New root has two children now.  Decide which of the
                // two children is going to have new key
                int i = 0;
                if (s.keys[0] < k)
                    i++;
                s.c[i].insertNonFull(k);

                // change root
                root = s;
            }
            else  // If root is not full, call insertNonFull for root
                root.insertNonFull(k);
        }
    }
    void remove(int k){
        if (root==null)
        {
            System.out.println("The tree is empty");
            return;
        }

        // call the remove function for root
        root.remove(k);

        // If the root node has 0 keys, make its first child as the new root
        //  if it has a child, otherwise set root as null
        if (root.n==0)
        {
            BTreeNode tmp = root;
            if (root.leaf)
                root = null;
            else
                root = root.c[0];

            // Free the old root
            tmp = null;
        }
        return;
    }
}
